package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;



/**
 * @author xiongmin
 * @version 0.0.1
 * @description Created by work on 2021/10/22 12:56 上午
 * @see
 */
public class MajorityElementII {


    /**
     * 暴力计算法
     * 1. 数组排序
     * 2. 计算出现次数超过n/3的数字
     * @param nums
     * @return
     */
    public List<Integer> majorityElement(int[] nums) {
        int len = nums.length;
        quickSort(nums,0,len-1);
        List<Integer> result = new ArrayList<>();
        int pre = nums[0], tag = 0;
        for (int i = 0; i < len; i++) {
            if (pre == nums[i]) {
                tag++;
            } else {
                if (tag * 3 > len) {
                    result.add(pre);
                }
                tag = 1;
                pre = nums[i];
            }
        }
        if (tag * 3 > len) {
            result.add(pre);
        }
        return result;
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int tagIndex = executeSort(nums,left,right);
            quickSort(nums,left,tagIndex-1);
            quickSort(nums,tagIndex+1, right);
        }
    }

    private int executeSort(int[] nums, int left, int right) {
        int tagValue = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= tagValue) right--;
            nums[left] = nums[right];
            while (left < right && nums[left] < tagValue) left++;
            nums[right] = nums[left];
        }
        nums[left] = tagValue;
        return left;
    }


    /**
     * 该算法用于1/2情况，它说：“在任何数组中，出现次数大于该数组长度一半的值只能有一个。”
     *
     * 那么，改进一下用于1/3。可以着么说：“在任何数组中，出现次数大于该数组长度1/3的值最多只有两个。”
     *
     * 于是，需要定义两个变量。空间复杂度为O(1)。
     *
     * 摩尔投票法：https://mabusyao.iteye.com/blog/2223195
     *
     * 算法1/3改进：https://blog.csdn.net/weixin_42768679/article/details/81567231
     *
     * @param nums
     * @return
     */
    public List<Integer> majorityElement2(int[] nums) {
        int len = nums.length;
        quickSort(nums,0,len-1);
        List<Integer> result = new ArrayList<>();
        int pre = nums[0], tag = 0;
        int tagDot = len/3;
        for (int i = 0; i < len; i++) {
            if (pre == nums[i]) {
                tag++;
            } else {
                if (tag > tagDot) {
                    result.add(pre);
                    if (result.size() >= 2) {
                        return result;
                    }
                }
                tag = 1;
                pre = nums[i];
            }
        }
        if (tag > tagDot) {
            result.add(pre);
        }
        return result;
    }


    /**
     * 摩尔投票法(抵消阶段，计算阶段)
     * 该算法用于1/2情况，它说：“在任何数组中，出现次数大于该数组长度一半的值只能有一个。”
     * 那么，改进一下用于1/3。可以着么说：“在任何数组中，出现次数大于该数组长度1/3的值最多只有两个。”
     * 于是，需要定义两个变量。空间复杂度为O(1)。
     * 摩尔投票法：https://mabusyao.iteye.com/blog/2223195
     * 算法1/3改进：https://blog.csdn.net/weixin_42768679/article/details/81567231
     * @param nums
     * @return
     */
    public List<Integer> majorityElement3(int[] nums) {
        int len = nums.length;
        List<Integer> result = new ArrayList<>();
        int tag1 = 0, tag2 = 0;
        int vote1 = 0, vote2 = 0;
        for (int i = 0; i < len; i++) {
            if (vote1 > 0 && tag1 == nums[i]) { // 第一个数累加
                vote1++;
            } else if (vote2 > 0 && tag2 == nums[i]) { // 第二个数累加
                vote2++;
            } else if (vote1 == 0) { // 选择第一个数
                tag1 = nums[i];
                vote1++;
            } else if (vote2 == 0) { // 选择第二个数
                tag2 = nums[i];
                vote2++;
            } else { // 抵消
                vote1--;
                vote2--;
            }
        }

        // 计算阶段，判断出现次数是否大于len/3
        int count1 = 0, count2 = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] == tag1) {
                count1++;
            }
            if (nums[i] == tag2) {
                count2++;
            }
        }
        if (count1 * 3 > len) {
            result.add(tag1);
        }
        if (count2 * 3 > len && tag1 != tag2) {
            result.add(tag2);
        }
        return result;
    }
}
